package tree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 */
public class Mytree {

    class TreeNode{
        public String value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(String value) {
            this.value = value;
        }
    }


    // 获取树中节点的个数
    private int nodeSize;
    public int size1(TreeNode root){
        if(root==null){
            return 0;
        }
        nodeSize++;
        size1(root.left);
        size1(root.right);
        return nodeSize;
    }

    // 子问题思路-求结点个数-左子树的节点加根节点和右子树的节点之和
    public int size2(TreeNode root){
        if(root==null){
            return 0;
        }
        return size2(root.left)+1+size2(root.right);
    }

    // 获取叶子节点的个数
    private int nodeLeafSize;
    int getLeafNodeCount1(TreeNode root){
        if(root==null){
            return 0;
        }
        if (root.left==null&&root.right==null){
            nodeLeafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
        return nodeLeafSize;
    }
    // 子问题思路-求叶子结点个数-左子树的叶子节点加右子树的叶子节点之和
    public int getLeafNodeCount2(TreeNode root){
        if(root==null){
            return 0;
        }
        if (root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+
                getLeafNodeCount2(root.right);
    }




    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) +
                getKLevelNodeCount(root.right,k-1);
    }




    // 获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }

        int leftHigh=getHeight(root.left);
        int rightHigh=getHeight(root.right);
        return Math.max(leftHigh,rightHigh)+1;
    }


    //判断是否为平衡二插树
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftHeight =getHeight(root.left);
        int rightHeight =getHeight(root.right);
        if(Math.abs(leftHeight-rightHeight)>=2){
            return false;
        }else{
            return isBalanced(root.left)&&isBalanced(root.right);
        }
    }


    // 检测值为value的元素是否存在
    public boolean find(TreeNode root, String val){
        if(root==null){
            return false;
        }
        if(root.value.equals(val)){
            return true;
        }
        return find(root.left,val)||
                find(root.right,val);

    }




    // 找到value值的节点
    public TreeNode find1(TreeNode root, String val){
        if(root==null){
            return null;
        }
        if(root.value.equals(val)){
            return root;
        }
        TreeNode leftN= find1(root.left,val);
        if(leftN!=null){
            return leftN;
        }
        TreeNode rightN= find1(root.right,val);
        if(rightN!=null){
            return rightN;
        }
        return null;
    }



    //层序遍历
    public void levelOrder(TreeNode root){
        if(root==null){
            return;
        }
        Queue<TreeNode> queue =new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur =queue.poll();
            System.out.print(cur.value+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

    //层次遍历2
    public List<List<String>> levelOrder1(TreeNode root) {
        List<List<String>> ret =new LinkedList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> node =new LinkedList<>();
        node.offer(root);
        while(!node.isEmpty()){
            int size=node.size();
            List<String> list =new LinkedList<>();
            while(size!=0){
                TreeNode cur =node.poll();
                list.add(cur.value);
                if(cur.left!=null){
                    node.offer(cur.left);
                }
                if(cur.right!=null){
                    node.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root==null){
           return true;
        }
        Queue<TreeNode> queue =new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur =queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            if (cur==null){
                break;
            }
        }
        while (!queue.isEmpty()){
            if(queue.poll()!=null){
                break;
            }
        }
        if(queue.isEmpty()){
            return true;
        }else {
            return false;
        }
    }



    //相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p!=null&&q==null||p==null&&q!=null){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.value==q.value){
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }else{
            return false;
        }
    }

    //是否是另一个树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }else{
            return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
        }
    }





    //判断是否为二插树
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSame(root.left,root.right);
    }
    public boolean isSame(TreeNode lefttree,TreeNode righttree){
        if(lefttree==null&&righttree==null){
            return true;
        }
        if(lefttree==null&&righttree!=null||lefttree!=null&&righttree==null){
            return false;
        }
        if(lefttree.value==righttree.value){
            return isSame(lefttree.left,righttree.right)&&isSame(lefttree.right,righttree.left);
        }else{
            return false;
        }
    }



    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp =root.left;
        root.left =root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }





    //找公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode lefttree =lowestCommonAncestor(root.left,p,q);
        TreeNode righttree =lowestCommonAncestor(root.right,p,q);
        if(lefttree!=null&&righttree!=null){
            return root;
        }
        if(lefttree!=null&&righttree==null){
            return lefttree;
        }
        if(lefttree==null&&righttree!=null){
            return righttree;
        }
        return null;
    }




   //根据前序遍历和中序遍历创建二叉树
    public TreeNode buildTree(String[] preorder, String[] inorder) {
        return buildTreeChild(preorder,0,preorder.length-1,inorder);
    }
    public int k=0;
    public TreeNode buildTreeChild(String[] preorder,int st,int ed, String[] inorder){
        if(st>ed){
            return null;
        }
        TreeNode node =new TreeNode(preorder[k]);
        int rootindex=findVal(preorder[k],inorder);
        k++;
        node.left=buildTreeChild(preorder,st,rootindex-1,inorder);
        node.right=buildTreeChild(preorder,rootindex+1,ed,inorder);
        return node;
    }
    public static int findVal(String value,String[] inorder){
        for(int j=0;j<inorder.length;j++){
            if(inorder[j]==value){
                return j;
            }
        }
        return -1;
    }




    //根据后序遍历和中序遍历创建二叉树
    public int i=0;
    public TreeNode buildTree2(String[]  inorder, String[] postorder) {
        i=postorder.length-1;
        return buildTreeChild2(postorder,0,postorder.length-1,inorder);
    }
    public TreeNode buildTreeChild2(String[] postorder,int st,int ed, String[] inorder){
        if(st>ed){
            return null;
        }
        TreeNode node =new TreeNode(postorder[i]);
        int rootindex=findVal2(postorder[i],inorder);
        i--;
        node.right=buildTreeChild2(postorder,rootindex+1,ed,inorder);
        node.left=buildTreeChild2(postorder,st,rootindex-1,inorder);
        return node;
    }
    public static int findVal2(String value,String[] inorder){
        for(int j=0;j<inorder.length;j++){
            if(inorder[j]==value){
                return j;
            }
        }
        return -1;
    }




    //根据前序序列创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder S =new StringBuilder();
        tree2strChild(S,root);
        return S.toString();
    }
    public void tree2strChild(StringBuilder S,TreeNode root){
        if(root==null){
            return ;
        }
        S.append(root.value);
        if(root.left!=null){
            S.append("(");
            tree2strChild(S,root.left);
            S.append(")");
        }else{
            if(root.right==null){
                return ;
            }
            S.append("()");
        }
        if(root.right!=null){
            S.append("(");
            tree2strChild(S,root.right);
            S.append(")");
        }else{
            if(root.right==null){
                return ;
            }
            S.append("()");
        }
    }



    //二叉搜索树变为双向链表
    public TreeNode pre=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        ConvertChild(pRootOfTree);
        while(pRootOfTree.left!=null){
            pRootOfTree=pRootOfTree.left;
        }
        return pRootOfTree;
    }
    public void ConvertChild(TreeNode root){
        if(root==null){
            return ;
        }
        ConvertChild(root.left);
        root.left=pre;
        if(pre!=null){
            pre.right=root;
        }
        pre=root;
        ConvertChild(root.right);
    }




    // 前序遍历
    public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.value+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //前序遍历返回链表
    public List<String> list =new ArrayList<>();
    public List<String> preorderTraversal1(TreeNode root) {
        if(root==null){
            return list;
        }
        list.add(root.value);
        preorderTraversal1(root.left);
        preorderTraversal1(root.right);
        return list;
    }
    public List<String> preorderTraversal2(TreeNode root) {
        List<String> list =new ArrayList<>();
        if(root==null){
            return list;
        }
        list.add(root.value);
        list.addAll(preorderTraversal2(root.left));
        list.addAll(preorderTraversal2(root.right));
        return list;
    }

    //递归
    public List<String> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack =new Stack<>();
        List<String> list =new ArrayList<>();
        TreeNode cur =root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                list.add(stack.peek().value);
                cur=cur.left;
            }
            TreeNode top =stack.pop();
            cur=top.right;
        }
        return list;
    }



    // 中序遍历
    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.value+" ");
        inOrder(root.right);
    }
    //中序遍历返回链表
    public List<String> list1 =new ArrayList<>();
    public List<String> inorderTraversal1(TreeNode root) {
        if(root==null){
            return list1;
        }
        inorderTraversal1(root.left);
        list1.add(root.value);
        inorderTraversal1(root.right);
        return list1;
    }
    public List<String> inorderTraversal2(TreeNode root) {
        List<String> list =new ArrayList<>();
        if(root==null){
            return list;
        }
        list.addAll(inorderTraversal2(root.left));
        list.add(root.value);
        list.addAll(inorderTraversal2(root.right));
        return list;
    }



    //递归
    public List<String> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack =new Stack<>();
        List<String> list =new ArrayList<>();
        TreeNode cur =root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top =stack.pop();
            list.add(top.value);
            cur=top.right;
        }
        return list;
    }





    //后序遍历
    public void lastOrder(TreeNode root){
        if(root==null){
            return;
        }
        lastOrder(root.left);
        lastOrder(root.right);
        System.out.print(root.value+" ");
    }
    //后序遍历返回链表
    List<String> list2 =new ArrayList<>();
    public List<String> postorderTraversal1(TreeNode root) {
        if(root==null){
            return list2;
        }
        postorderTraversal1(root.left);
        postorderTraversal1(root.right);
        list2.add(root.value);
        return list2;
    }
    public List<String> postorderTraversal2(TreeNode root) {
        List<String> list =new ArrayList<>();
        if(root==null){
            return list;
        }
        list.addAll(postorderTraversal2(root.left));
        list.addAll(postorderTraversal2(root.right));
        list.add(root.value);
        return list;
    }



    //递归
    public List<String> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack =new Stack<>();
        List<String> list =new ArrayList<>();
        TreeNode cur =root;
        TreeNode pre =null;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top =stack.peek();
            if(top.right==null ||top.right==pre){
                TreeNode ret= stack.pop();
                list.add(ret.value);
                pre =top;
            }else{
                cur=top.right;
            }
        }
        return list;
    }




    public TreeNode creatTree(){
        TreeNode nodeA = new TreeNode("A");
        TreeNode nodeB=  new TreeNode("B");
        TreeNode nodeC = new TreeNode("C");
        TreeNode nodeD = new TreeNode("D");
        TreeNode nodeE = new TreeNode("E");
        TreeNode nodeF = new TreeNode("F");
        TreeNode nodeG = new TreeNode("G");
        TreeNode nodeH = new TreeNode("H");
        nodeA.left=nodeB;
        nodeA.right=nodeC;
        nodeB.left=nodeD;
        nodeB.right=nodeE;
        nodeC.left=nodeF;
        nodeC.right=nodeG;
        nodeE.right=nodeH;
        return nodeA;
    }


//    public static int i= 0;
//    public static TreeNode creatPreOrder(String s){
//        Character ch =s.charAt(i);
//        TreeNode node =null;
//        if(ch!='#'){
//            node =new TreeNode(ch);
//            i++;
//            node.left=creatPreOrder(s);
//            node.right=creatPreOrder(s);
//        }else{
//            i++;
//        }
//        return node;
//    }
}
